package Offer2017;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树中和为某值的路径
 * Created by 雷文康 on 2018/1/1.
 */
public class Test25 {

    public static void main(String[] args) {
        TreeNode node1=new TreeNode(10);
        TreeNode node2=new TreeNode(5);
        TreeNode node3=new TreeNode(12);
        TreeNode node4=new TreeNode(4);
        TreeNode node5=new TreeNode(7);
        node1.left=node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        node3.left=node3.right=null;
        node4.left=node4.right=null;
        node5.left=node5.right=null;
        findPath(node1,22);
    }

    public static void findPath(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        ArrayList<Integer> list = new ArrayList<>();
        findPath(root, target, list, 0);
    }

    private static void findPath(TreeNode root, int target, ArrayList<Integer> list, int sum) {
         list.add(root.value);
         sum += root.value;
         boolean isLeaf = root.left == null && root.right == null;
         if (isLeaf && sum == target){
             System.out.print("找到路径");
             //遍历List
             for (int i = 0; i < list.size(); i++) {
                 System.out.print(list.get(i));
                 System.out.print(" ");
             }
         }
         if (root.left != null){
             findPath(root.left, target, list, sum);
         }
         if (root.right != null){
             findPath(root.right, target, list, sum);
         }
         list.remove(list.size() - 1);
         sum -= root.value;
    }
}
